package sort

import (
	"math/rand"
)

/**
 * @Description: 堆排序，维护堆的性质
 * @Keyword: TODO
 * @Author: kami
 * @Date: 2022/8/9 6:52
 **/
func heapify(arr []int, n, i int) {
	var largest = i
	var left = 2*i + 1
	var right = 2*i + 2
	if left < n && arr[largest] < arr[left] {
		largest = left
	}
	if right < n && arr[largest] < arr[right] {
		largest = right
	}
	if largest != i {
		arr[largest], arr[i] = arr[i], arr[largest]
		heapify(arr, n, largest)
	}
}

func heapSort(arr []int) {
	var n = len(arr)
	for i := n / 2; i >= 0; i-- {
		heapify(arr, n, i)
	}
	for i := n - 1; i > 0; i-- {
		arr[i], arr[0] = arr[0], arr[i]
		heapify(arr, i, 0)
	}
}

func quickSortV4(nums []int) {
	quickSearch(nums, 0, len(nums)-1)
}

func quickSearch(nums []int, left, right int) {
	if left >= right {
		return
	}
	var povitIdx = rand.Intn(right-left+1) + left
	nums[left], nums[povitIdx] = nums[povitIdx], nums[left]
	partition(nums, left, right)
}
func partition(nums []int, left, right int) {
	if left < right {
		var povitVal = nums[left]
		var low = left
		var high = right
		for low < high {
			for low < high && nums[high] > povitVal {
				high--
			}
			for low < high && nums[low] < povitVal {
				low++
			}
			if low < high {
				nums[low], nums[high] = nums[high], nums[low]
			}
		}
		nums[low] = povitVal
		quickSearch(nums, left, low-1)
		quickSearch(nums, low+1, right)
	}
}
